#include <iostream>
using namespace std;

//brute force methond to find all inverse numbers
int brute_inverse_numbers(int *arr, unsigned int length)
{
	int sum = 0;
	int i, j;
	for (i = 0; i < length; ++i)
	{
		for (j = i + 1; j < length; ++j)
		{
			//if the current number is less than the pivot,
			//then the sum plus one
			if (arr[j] < arr[i])
			{
				sum++;
			}
		}
	}
	return sum;
}

int merge(int *arr, int start, int middle, int end)
{
	int leftLength = middle -start + 1;
	int rightLength = end - middle;
	int *left = new int[leftLength];
	int *right = new int[rightLength];
	int i, sum = 0;
	for (i = 0; i < leftLength; ++i)
	{
		left[i] = arr[start + i];
	}

	for (i = 0; i < rightLength; ++i)
	{
		right[i] = arr[middle + 1 + i];
	}

	i = 0;
	int j = 0, k = start;
	while(i < leftLength && j < rightLength ) {
		if (left[i] < right[j])
		{
			arr[k++] = left[i++];
		}
		else 
		{
			arr[k++] = right[j++];
			sum = sum + leftLength - i;
		}
	}
	if (i < leftLength )
	{
		while(i < leftLength ) {
			arr[k++] = left[i++];
		}
	}
	else {
		while(j < rightLength) {
			arr[k++] = right[j++];
		}
	}
	return sum;
}

int merge_sort_inverse_number(int *arr, int start, int end)
{
	if (start >= end)
	{
		return 0;
	}
	int middle = (end + start)/2;
	int leftSum = merge_sort_inverse_number(arr, start, middle);
	int rightSum = merge_sort_inverse_number(arr, middle + 1, end);
	int sum = leftSum + rightSum + merge(arr, start, middle, end);
	return sum;
}

int main(int argc, char *argv[])
{
	int arr[] = {2, 4, 3, 1};
	/*cout << "the inverse number of the array is " << 
		brute_inverse_numbers(arr, sizeof(arr)/sizeof(int)) << endl;*/
	cout << merge_sort_inverse_number(arr, 0, 3) << endl;
	cout << arr[0] << ", " << arr[1] << ", " << arr[2] << ", " <<arr[3] << endl; 
	return 0;
}
